package com.lee.algorithm.recursion;

/***
 * @description: 汉诺塔
 * @author : 汉诺塔
 * @date: 2021/12/17 20:24
 */
public class Hanoi {

    /**
     * @param n 层数
     */
    public static void hanoi(int n) {
        if (n > 0) {
            move(n, "左", "中", "右");
        }
    }

    /**
     * 1 ~ level 圆盘，left -> right，mid 是另一个
     *
     * 1、把 1 ~ level-1 从 left 移到 mid
     * 2、把 level 从 left 移到 right
     * 3、把 1 ~ level-1 从 mid 移回 left
     * 4、重复 1 ~ 3 步
     * @param level
     * @param left
     * @param mid
     * @param right
     */
    private static void move(int level, String left, String mid, String right) {
        if (level == 1) {
            System.out.println("Move 1 from " + left + " to " + right);
        } else {
            move(level - 1, left, mid, right);
            System.out.println("Move " + level + " from " + left + " to " + right);
            move(level - 1, mid, right, left);
        }
    }

    public static void main(String[] args) {
        hanoi(3);
    }
}
